Flash memory is used in a wide variety of products including many types of computing, communication, and consumer electronic devices. Flash memory is a type of nonvolatile memory. Flash memory has been used as file systems for storing data. One such system is the Flash Data Integrator (FDI), which has been used in cell phones and other electronic devices.
The FDI is one embodiment of a flash file system. It consists of paragraph object space, page object space and the free flash pool. FIG. 1 depicts a basic memory map layout. The managed space is the location in the memory block between the lowest address and the highest address. The page object space 11 generally resides at the bottom of the flash memory space 10 and has the lowest address location. The free flash pool 12, or unused flash space, resides on top of the page object space 11. The highest address is the paragraph object space 13, where the page and paragraph object headers are stored. When either the paragraph object space 13 or page object space 11 requires more flash memory space, it takes an entire block from the free flash pool 12.
An object is a method of storing data. In a flash memory block, each object is split into a specific size. In order to write objects to flash memory, allocation of memory space is necessary to ensure that sufficient memory is available to satisfy a request. A memory block may contain an unlimited number of objects. An allocation process performs available memory calculations to determine whether a request can be granted without violating the allocation requirements. De-allocation is needed in order to allow the user to discard an allocated object. This is done by marking the object as “invalid.” The memory space is reclaimed during the reclamation part of the de-allocation process. Reclamation occurs during every de-allocation to compress and keep all the objects contiguous in memory.
The reclaim block 14 resides above the managed space. During reclaim, the reclaim block 14 is used for temporary storage of objects. Reclaim is the process of cleaning up all the dirty space in the flash by erasing the space associated with previously used flash memory space. In other words, reclaim erases flash memory associated with de-allocated objects. Every time an object is de-allocated in flash, the de-allocated memory becomes dirty space. To reuse the dirty space, the entire block needs to be erased. The reclaim process involves moving all the valid data into the free flash pool 12, erasing the block, and copying back the data back into the object space.
Flash file systems, such as FDI, often need to support numerous applications. K-Java is one such application. In FDI, K-Java files are stored as objects. A K-Java object may contain internal pointers that reference data within the object or other K-Java objects. These internal pointers may contain physical flash addresses to improve K-Java performance. The file system must ensure that the K-Java reference made via the physical flash address is always valid. Address validity is threatened by the file system reclaim process described previously. This is because the reclaim process can move the object to a new physical flash address, rendering some K-Java internal pointers obsolete. The file system must provide a mechanism to correct the obsolete pointers before they are used.
In addition, the data of each K-Java file must be contiguous in memory space. Many flash file systems fragment file data so that the fragment size is equal to or less than the flash block size. This is inadequate for K-Java file support. A K-Java file must be able to span multiple flash blocks, if necessary to maintain contiguous file data. Therefore, there are advantages to having a reclaim method that compresses space so that the created free space is contiguous.